home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Programming / vahunz / source / ubiqx / ubi_BinTree.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-04-17  |  6.1 KB  |  391 lines
  1. /*
  2.  * This source file is part of Vahunz,
  3.  * a tool to make source code un-/more legible.
  4.  *
  5.  *--------------------------------------------------------------------------
  6.  *
  7.  * Vahunz and the Ugly library are Copyright (C) 1998 by
  8.  * Thomas Aglassinger <agi@giga.or.at>
  9.  *
  10.  * All rights reserved.
  11.  *
  12.  * Refer to the manual for more information.
  13.  *
  14.  *--------------------------------------------------------------------------
  15.  *
  16.  * Ubiqx library is Copyright (C) 1991-1998 by
  17.  * Christopher R. Hertel <crh@ubiqx.mn.org>
  18.  *
  19.  * Ubiqx library is free software; you can redistribute it and/or
  20.  * modify it under the terms of the GNU Library General Public
  21.  * License as published by the Free Software Foundation; either
  22.  * version 2 of the License, or (at your option) any later version.
  23.  *
  24.  */
  25. #include "ubi_BinTree.h" 
  26. #include <stdlib.h> 
  27. static char f2A[] = "ubi_BinTree\n\
  28. \t$Revision: 2.5 $\n\
  29. \t$Date: 1997/12/23 03:56:29 $\n\
  30. \t$Author: crh $\n";
  31. static l1Z l4I( w7Nt m3Sk,
  32. f7P m9X,
  33. register l1Z p )
  34. {
  35. long e0Y;
  36. while( p && (( e0Y = f2V((*m3Sk)(m9X, p)) ) != t3Db) )
  37. p = p->b9H[e0Y];
  38. return( p );
  39. } 
  40. static l1Z p7Q( f7P j3I,
  41. l1Z p,
  42. l1Z *t6Z,
  43. char *k5O,
  44. w7Nt q6X )
  45. {
  46. register l1Z t6V = p;
  47. l1Z x2Ez = NULL;
  48. int h1J = t3Db;
  49. int t1W;
  50. while( t6V
  51. && (t3Db != (t1W = f2V((*q6X)(j3I, t6V)))) )
  52. {
  53. x2Ez = t6V; 
  54. h1J = t1W; 
  55. t6V = t6V->b9H[t1W]; 
  56. }
  57. *t6Z = x2Ez; 
  58. *k5O = h1J;
  59. return( t6V );
  60. } 
  61. static void l9H( l1Z *e2L,
  62. l1Z k7H,
  63. l1Z t2M )
  64. {
  65. register int i;
  66. register int g4D = sizeof( c9M );
  67. for( i = 0; i < g4D; i++ ) 
  68. ((unsigned char *)t2M)[i] = ((unsigned char *)k7H)[i];
  69. (*e2L) = t2M; 
  70. if( k7H->b9H[z7V] )
  71. (k7H->b9H[z7V])->b9H[z6Y] = t2M;
  72. if( k7H->b9H[i7C] )
  73. (k7H->b9H[i7C])->b9H[z6Y] = t2M;
  74. } 
  75. static void q7H( o4R x8O,
  76. l1Z v6L,
  77. l1Z h3D )
  78. {
  79. l1Z *Parent;
  80. c9M u4M;
  81. l1Z v3O = &u4M;
  82. if( v6L->b9H[z6Y] )
  83. Parent = &((v6L->b9H[z6Y])->b9H[(int)(v6L->k5O)]);
  84. else
  85. Parent = &(x8O->k6P);
  86. l9H( Parent, v6L, v3O );
  87. if( h3D->b9H[z6Y] )
  88. Parent = &((h3D->b9H[z6Y])->b9H[(int)(h3D->k5O)]);
  89. else
  90. Parent = &(x8O->k6P);
  91. l9H( Parent, h3D, v6L );
  92. if( v3O->b9H[z6Y] )
  93. Parent = &((v3O->b9H[z6Y])->b9H[(int)(v3O->k5O)]);
  94. else
  95. Parent = &(x8O->k6P);
  96. l9H( Parent, v3O, h3D );
  97. } 
  98. static l1Z b7K( register l1Z P,
  99. register int i8L )
  100. {
  101. l1Z Q = NULL;
  102. while( P )
  103. {
  104. Q = P;
  105. P = P->b9H[ i8L ];
  106. }
  107. return( Q );
  108. } 
  109. static l1Z u9X( register l1Z P,
  110. register int i8L )
  111. {
  112. if( P )
  113. {
  114. if( P->b9H[ i8L ] )
  115. return( b7K( P->b9H[ i8L ], (char)y2Bn(i8L) ) );
  116. else
  117. while( P->b9H[ z6Y ] )
  118. {
  119. if( (P->b9H[ z6Y ])->b9H[ i8L ] == P )
  120. P = P->b9H[ z6Y ];
  121. else
  122. return( P->b9H[ z6Y ] );
  123. }
  124. }
  125. return( NULL );
  126. } 
  127. static l1Z Border( o4R x8O,
  128. f7P m9X,
  129. l1Z p,
  130. int i8L )
  131. {
  132. register l1Z q;
  133. if( !p3K( x8O ) || (z6Y == i8L) )
  134. return( p );
  135. q = p->b9H[z6Y];
  136. while( q && (t3Db == f2V( (*(x8O->m3Sk))(m9X, q) )) )
  137. {
  138. p = q;
  139. q = p->b9H[z6Y];
  140. }
  141. q = p->b9H[i8L];
  142. while( q )
  143. {
  144. q = l4I( x8O->m3Sk, m9X, q );
  145. if( q )
  146. {
  147. p = q;
  148. q = p->b9H[i8L];
  149. }
  150. }
  151. return( p );
  152. } 
  153. long t2S( register long x )
  154. {
  155. return( (x)?((x>0)?(1):(-1)):(0) );
  156. } 
  157. l1Z u3Ny( l1Z y2B )
  158. {
  159. y2B->b9H[ z7V ] = NULL;
  160. y2B->b9H[ z6Y ] = NULL;
  161. y2B->b9H[ i7C ] = NULL;
  162. y2B->k5O = t3Db;
  163. return( y2B );
  164. } 
  165. o4R q4C( o4R x8O,
  166. w7Nt b2W,
  167. unsigned char Flags )
  168. {
  169. if( x8O )
  170. {
  171. x8O->k6P = NULL;
  172. x8O->count = 0L;
  173. x8O->m3Sk = b2W;
  174. x8O->flags = (Flags & r9O) ? r9O : Flags;
  175. } 
  176. return( x8O );
  177. } 
  178. f6W k2M( o4R x8O,
  179. l1Z j4E,
  180. f7P j7S,
  181. l1Z *s3L )
  182. {
  183. l1Z r9V,
  184. e2L = NULL;
  185. char e0Y;
  186. if( !(s3L) ) 
  187. s3L = &r9V;
  188. (void)u3Ny( j4E ); 
  189. *s3L = p7Q(j7S, (x8O->k6P), &e2L, &e0Y, (x8O->m3Sk));
  190. if (!(*s3L)) 
  191. {
  192. if (!(e2L))
  193. x8O->k6P = j4E;
  194. else
  195. {
  196. e2L->b9H[(int)e0Y] = j4E;
  197. j4E->b9H[z6Y] = e2L;
  198. j4E->k5O = e0Y;
  199. }
  200. (x8O->count)++;
  201. return( s0E );
  202. }
  203. if( p3K(x8O) ) 
  204. {
  205. l1Z q;
  206. e0Y = i7C;
  207. q = (*s3L);
  208. *s3L = NULL;
  209. while( q )
  210. {
  211. e2L = q;
  212. if( e0Y == t3Db )
  213. e0Y = i7C;
  214. q = q->b9H[(int)e0Y];
  215. if ( q )
  216. e0Y = f2V( (*(x8O->m3Sk))(j7S, q) );
  217. }
  218. e2L->b9H[(int)e0Y] = j4E;
  219. j4E->b9H[z6Y] = e2L;
  220. j4E->k5O = e0Y;
  221. (x8O->count)++;
  222. return( s0E );
  223. }
  224. if( b4Y(x8O) ) 
  225. {
  226. if (!(e2L))
  227. l9H( &(x8O->k6P), *s3L, j4E );
  228. else
  229. l9H( &(e2L->b9H[(int)((*s3L)->k5O)]),
  230. *s3L, j4E );
  231. return( s0E );
  232. }
  233. return( b9P ); 
  234. } 
  235. l1Z v6T( o4R x8O,
  236. l1Z b2L )
  237. {
  238. l1Z p,
  239. *t6Z;
  240. int e0Y;
  241. if( (b2L->b9H[z7V]) && (b2L->b9H[i7C]) )
  242. q7H( x8O, b2L, l7C( b2L ) );
  243. if (b2L->b9H[z6Y])
  244. t6Z = &((b2L->b9H[z6Y])->b9H[(int)(b2L->k5O)]);
  245. else
  246. t6Z = &( x8O->k6P );
  247. e0Y = ((b2L->b9H[z7V])?z7V:i7C);
  248. p = (b2L->b9H[e0Y]);
  249. if( p )
  250. {
  251. p->b9H[z6Y] = b2L->b9H[z6Y];
  252. p->k5O = b2L->k5O;
  253. }
  254. (*t6Z) = p;
  255. (x8O->count)--;
  256. return( b2L );
  257. } 
  258. l1Z p2P( o4R x8O,
  259. f7P m9X,
  260. w3K w5Y )
  261. {
  262. register l1Z p;
  263. l1Z e2L;
  264. char p4Ny;
  265. p = p7Q( m9X,
  266. x8O->k6P,
  267. &e2L,
  268. &p4Ny,
  269. x8O->m3Sk );
  270. if( p ) 
  271. {
  272. switch( w5Y )
  273. {
  274. case g0I: 
  275. p = Border( x8O, m9X, p, z7V );
  276. return( u9X( p, z7V ) );
  277. case e6B: 
  278. p = Border( x8O, m9X, p, i7C );
  279. return( u9X( p, i7C ) );
  280. default:
  281. p = Border( x8O, m9X, p, z7V );
  282. return( p );
  283. }
  284. }
  285. if( j2M == w5Y ) 
  286. return( NULL ); 
  287. if( (g0I == w5Y) || (u4I == w5Y) )
  288. return( (z7V == p4Ny) ? u9X( e2L, p4Ny ) : e2L );
  289. else
  290. return( (i7C == p4Ny) ? u9X( e2L, p4Ny ) : e2L );
  291. } 
  292. l1Z f9B( o4R x8O,
  293. f7P m9X )
  294. {
  295. return( l4I( x8O->m3Sk, m9X, x8O->k6P ) );
  296. } 
  297. l1Z l1X( l1Z P )
  298. {
  299. return( u9X( P, i7C ) );
  300. } 
  301. l1Z l7C( l1Z P )
  302. {
  303. return( u9X( P, z7V ) );
  304. } 
  305. l1Z o7R( l1Z P )
  306. {
  307. return( b7K( P, z7V ) );
  308. } 
  309. l1Z d4K( l1Z P )
  310. {
  311. return( b7K( P, i7C ) );
  312. } 
  313. l1Z g1V( o4R x8O,
  314. f7P n8U,
  315. l1Z p )
  316. {
  317. if( !p || f2V( (*(x8O->m3Sk))( n8U, p ) != t3Db ) )
  318. return( NULL );
  319. return( Border( x8O, n8U, p, z7V ) );
  320. } 
  321. l1Z z5H( o4R x8O,
  322. f7P n8U,
  323. l1Z p )
  324. {
  325. if( !p || f2V( (*(x8O->m3Sk))( n8U, p ) != t3Db ) )
  326. return( NULL );
  327. return( Border( x8O, n8U, p, i7C ) );
  328. } 
  329. f6W b6S( o4R x8O,
  330. c7W d2L,
  331. void *UserData )
  332. {
  333. l1Z p;
  334. if( !(p = o7R( x8O->k6P )) ) return( b9P );
  335. while( p )
  336. {
  337. (*d2L)( p, UserData );
  338. p = l1X( p );
  339. }
  340. return( s0E );
  341. } 
  342. f6W q1C( o4R x8O,
  343. r2L q1P )
  344. {
  345. l1Z p, q;
  346. if( !(x8O) || !(q1P) )
  347. return( b9P );
  348. p = o7R( x8O->k6P );
  349. while( p )
  350. {
  351. q = p;
  352. while( q->b9H[i7C] )
  353. q = b7K( q->b9H[i7C], z7V );
  354. p = q->b9H[z6Y];
  355. if( p )
  356. p->b9H[ ((p->b9H[z7V] == q)?z7V:i7C) ] = NULL;
  357. (*q1P)((void *)q);
  358. }
  359. (void)q4C( x8O,
  360. x8O->m3Sk,
  361. x8O->flags );
  362. return( s0E );
  363. } 
  364. l1Z s6Y( l1Z f5Y )
  365. {
  366. l1Z x1M = NULL;
  367. int i8L = z7V;
  368. while( NULL != f5Y )
  369. {
  370. x1M = f5Y;
  371. f5Y = x1M->b9H[ i8L ];
  372. if( NULL == f5Y )
  373. {
  374. i8L = y2Bn( i8L );
  375. f5Y = x1M->b9H[ i8L ];
  376. }
  377. }
  378. return( x1M );
  379. } 
  380. int x0K( int c8H, char *list[] )
  381. {
  382. if( c8H > 0 )
  383. {
  384. list[0] = f2A;
  385. if( c8H > 1 )
  386. list[1] = NULL;
  387. return( 1 );
  388. }
  389. return( 0 );
  390. } 
  391.